package com.jxb.four;

import com.jxb.tree.TreeNode;

/**
 * 把二叉搜索树转换为累加树
 * 节点值 = 大于当前节点的所有节点值之和
 * 输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
 * 输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
 *
 * 思路：
 *  1：若是root节点，当前节点值等于所有右子树节点值之和 + 当前节点值
 *  2：若是右子树节点，当前节点值等于所有右子树节点值之和 + 当前节点值
 *  3：若是左子树节点，上一次节点的值 + 当前节点所有右子树节点值之和 + 当前节点值
 *
 * 实现逻辑：
 *  通过中序遍历来累加
 */
public class ConvertBSTtoGT_538 {

    public static void main(String[] args) {

    }

    int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        accessTree(root);
        return root;
    }


//    public void accessTree1(TreeNode root) {
//        if (root == null) {
//            return;
//        }
//        accessTree1(root.right);
//        root.val = root.val + sum;
//        sum = root.val;
//        accessTree1(root.left);
//    }


    public void accessTree(TreeNode root) {
        if (root == null) {
            return;
        }
        accessTree(root.right);
        root.val += sum;
        sum = root.val;
        accessTree(root.left);
    }

}
